/* 
 * Longest Valid Parentheses
 * Given a string containing just the characters '(' and ')', find the length of the longest valid parentheses substring
 * example ")()())", where the longest parentheses substring is "()()", length=4
 */

#include "../func.h"

int longestValidParentheses(const string &s)
{
    int max_len = 0, last = -1;
    stack<int> lefts;

    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == '(')
            lefts.push(i);
        else
        {
            if (lefts.empty())
                last = i;
            else
            {
                lefts.pop();
                if (lefts.empty())
                    max_len = max(max_len, i - last);
                else
                    max_len = max(max_len, i - lefts.top());
            }
        }
    }
    return max_len;
}

/* 
 * dp
 */
int longestvalidParentheses2(string &s)
{
    vector<int> f(s.size(), 0);
    int ret = 0;
    for (int i = s.size() - 2; i >= 0; --i)
    {
        int match = i + f[i + 1] + 1;
        if (s[i] == '(' && match < s.size() && s[match] == ')')
        {
            f[i] = f[i + 1] + 2;
            if (match + 1 < s.size())
                f[i] += f[match + 1];
        }
        ret = max(ret, f[i]);
    }
    return ret;
}

//todo
int longestValidParentheses3(const string &s)
{
    int answer = 0, depth = 0, start = -1;
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == '(')
        {
            ++depth;
        }
        else
        {
            --depth;
            if (depth < 0)
            {
                start = i;
                depth = 0;
            }
            else if (depth == 0)
            {
                answer = max(answer, i - start);
            }
        }
    }
    depth = 0;
    start = s.size();
    for (int i = s.size() - 1; i >= 0; --i)
    {
        if (s[i] == ')')
        {
            ++depth;
        }
        else
        {
            --depth;
            if (depth < 0)
            {
                start = i;
                depth = 0;
            }
            else if (depth == 0)
            {
                answer = max(answer, start - i);
            }
        }
    }
    return answer;
}